﻿using System;
using System.Collections.Generic;
using System.Text;

namespace Graphs
{
    /// <summary>
    /// 广度优先搜索
    /// </summary>
    public class BreadthFirstPaths
    {
        private bool[] marked;//到达该顶点的最短路径已知吗？
        private int[] edgeTo;//到达该顶点的已知路径上的最后一个顶点
        private int s;//起点

        public BreadthFirstPaths(Graph G,int s)
        {
            marked = new bool[G.V()];
            edgeTo = new int[G.V()];
            this.s = s;
            Bfs(G,s);
        }

        private void Bfs(Graph G, int s)
        {
            Queue<int> queue = new Queue<int>();
            marked[s] = true;//标记起点
            queue.Enqueue(s);//将它加入队列
            while (queue.Count > 0)
            {
                int v = queue.Dequeue();//从队列中删去下一个顶点
                foreach (var w in G.Adj(v))
                {
                    if (!marked[w])//对于每个未标记的相邻顶点
                    {
                        edgeTo[w] = v;//保存最短路径的最后一条边
                        marked[w] = true;//标记它，因为最短路径已知
                        queue.Enqueue(w);//并将它添加到队列中
                    }
                }
            }
        }

        public bool HasPathTo(int v)
        {
            return marked[v];
        }
    }
}
